package EnterpriseAlgorithm.Stack_Queue.Code.SlidingWindowMaximum;

import java.util.LinkedList;

class Solution2_ii {
    public int[] maxSlidingWindow(int[] arr, int w) {
        // 不符条件数组输入检查
        if (arr == null || arr.length == 0 || w < 0) {
            return null;
        }
        LinkedList<Integer> qMax = new LinkedList<>(); // 使用链表结构

        int[] res = new int[arr.length - w + 1];
        int index = 0; //记录结果数组下标

        // 遍历数组
        for (int i = 0; i < arr.length; i++) {

            // 加入元素前先判断 qMax是否为空，和与qMax队尾元素比较
            while (!qMax.isEmpty() && arr[qMax.peekLast()] < arr[i]) {
                qMax.pollLast();
            }

            //把下标 i 加入到deque中
            qMax.addLast(i);

            //当i增长到符合第一个k范围的时候，每滑动一步都将队列头节点放入结果就行了
            if (i >= w - 1) {
                res[index++] = arr[qMax.peekFirst()];
            }
        }
        return res;
    }
}